1. Field of the Invention
The present invention relates to a method and an apparatus for detecting collision between a plurality of virtual objects in a virtual space.
2. Description of the Related Art
Three-dimensional (3D) computer graphics (CG) technology has been used with the development thereof in various fields, and recently, has also been actively used in the fields of VR (Virtual Reality) and MR (Mixed Reality) as well as 3D-CAD (Computer-Aided Design).
In some applications of these fields, it is necessary to not only three-dimensionally represent virtual objects by CG but also consider collision of virtual objects with each other.
For example, in design using 3D-CAD, when a component represented as a virtual object collides with another component (multiple components occupy the same space), actual production is not possible. Therefore, during design it is checked if components collide with each other. Specifically, a method is used in which collisions are checked all at once with a specific component layout, and this method is referred to as static collision check. In addition, in the case of an apparatus with a movable portion, there is also a method in which collisions with other components are checked while running a mechanical simulation on the movable portion, and this method is referred to as dynamic collision check.
In the case of the dynamic collision check, the position and orientation which can be taken by the movable component is limited. Therefore, it is possible to take time for computing collisions, save the results as historical information, and represent the results to a user after the completion of total computation. The same applies to the static collision check described above.
In a design application using 3D-CAD, objects to be checked if there are collisions or not (hereinafter, referred to as target objects) are components of an apparatus, and it is usually the case that the possible position and orientation of the target objects are fixed, or sufficiently limited even for the target objects are movable. Therefore, it is also possible to carry out collision check exhaustively for the position and orientation which can be taken by the target objects.
However, in a VR or MR application, one of target objects can take many more positions and orientations, such as, for example, a tool held and operated in a user's hand or the user's hand itself, as compared with components as target objects in 3D-CAD.
For example, in the case of a VR or MR application for the purpose of manufacturing training for a product, collisions of a tool held in a user's hand with objects to be assembled such as components may be checked to feed back the results to the user, in order to give the user a sense of the actual assembly work.
In this case, the positions and orientations which can be taken by the tool held in the user's hand have six degrees of freedom in total, three degrees of freedom for parallel translation components and three degrees of freedom for rotational components, and thus are not substantially limited in the virtual space. Therefore, it is impossible to carry out a collision check in advance for all of the positions and orientations which can be taken by the target objects.
Accordingly, on a case-by-case basis, it is necessary to carry out a collision check in real time, based on the positions and orientations of the target objects.
Since the computations involved in collision checking (collision computation) represent a very high computation load, approaches have been proposed for carrying out such computations in real time. One of the most commonly used approaches is that “collision calculation is not carried out for objects which definitely do not collide with each other”. This approach is highly effective for collision computation in real time because unnecessary computation is not carried out.
As an example of this approach, a technique called Sweep and Prune (SAP) is well known. This SAP is a technique in which combinations of virtual objects for which bounding boxes definitely do not overlap are excluded from consideration as candidates for collision computation when a plurality of virtual objects (CG objects) are arranged in world coordinates.
When it is assumed that the world coordinates are represented in an XYZ orthogonal coordinate system, virtual objects for which projections of bounding boxes onto the X axis definitely do not overlap are free from the possibility of colliding with each other, and thus excluded as candidates for collision computation. Next, a similar check is carried out for projections onto the Y axis and projections onto the Z axis. Only combinations of virtual objects for which overlaps of bounding boxes are confirmed on all of the axes are subjected to collision calculation.
However, the bounding boxes are boxes surrounding the actual virtual objects, and thus larger than the actual virtual objects. Therefore, in SAP, in which whether or not collision computation is necessary is determined based on whether or not there is a collision between the bounding boxes, it is often the case that collision computation for combinations of virtual objects which do not actually collide with each other is not completely excluded.
In addition to such an approach for reducing objects to be subjected to collision computation, approaches for speeding up collision computation itself have been also proposed. In many of the approaches for speeding up computation, it is assumed that the target objects are convexity objects. The reason why collision computation is carried out at high speed for convexity objects is not directly related to the present invention, and a detailed description thereof will be thus omitted. It is to be noted that since there are actually virtual objects of concavity objects, relatively heavy preprocessing for decomposing target objects into convexity objects is required in order to use a collision computation approach using this approach for speeding up collision computation.
As described above, in the approach for speeding up collision computation with the assumption that target objects are convexity objects, relatively heavy preprocessing for the target objects into the convexity objects is required. Further, the amount of data after the reprocessing is comparable to the amount of data before the reprocessing. Thus, when this data amount becomes a problem, special measures are required for holding the data.
In addition, Japanese Patent Laid-Open No. 11-328445 describes a method for carrying out collision computation under the condition that collision calculation is carried out within ultimate rendering on an image plane. In this approach, collision computation can be carried out during rendering of virtual objects, and high-speed computation is thus enabled by carrying out computation in a GPU (Graphics Processing Unit). However, the approach described in Japanese Patent Laid-Open No. 11-328445 is not capable of widely application because collision detection is carried out by a collision detection means for each pixel by holding an arrangement of depths of objects for each pixel of a projection image and using a list of depths of overlapped pixels in the projection image. Therefore, it is difficult to apply this approach to collision detection for an ordinary group of virtual objects.